package org.demo.algorithm;


/**
 * 双向链表
 * @author  
 * @date    2011-4-24
 * @file    org.demo.algorithm.DoubleLinkedList.java
 */
public class DoubleLinkedList<E> {
	
	// 头节点
	private Node head = new Node(null);
	
	/**
	 * 添加到第一个
	 * @param val
	 */
	public DoubleLinkedList<E> addFirst(E val){
		Node cur = new Node(val);
		
		cur.prev = head;
		cur.next = head.next;
		cur.prev.next = cur;
		if (cur.next != null){
			cur.next.prev = cur;
		}
		return this;
	}
	/**
	 * 添加到最后一个
	 * @param val
	 */
	public DoubleLinkedList<E> addLast(E val){
		Node cur = new Node(val);
		
		Node last = head;
		while(last.next != null){
			last = last.next;
		}
		
		last.next = cur;
		cur.prev = last;
		return this;
	}
	/**
	 * 添加到指定节点之后
	 * @param node
	 * @param val
	 */
	public DoubleLinkedList<E> addAfter(Node node, E val){
		Node cur = new Node(val);
		
		cur.prev = node;
		cur.next = node.next;
		cur.prev.next = cur;
		if (cur.next != null){
			cur.next.prev = cur;
		}
		return this;
	}
	/**
	 * 获取节点
	 * @param val
	 * @return
	 */
	public Node getNode(E val){
		Node cur = head.next;
		while (cur != null && !val.equals(cur.value)){
			cur = cur.next;
		}
		return cur;
	}
	/**
	 * toString
	 */
	public String toString(){
		StringBuilder sb = new StringBuilder();
		sb.append('[');
		Node cur = head.next;
		while (cur != null){
			if (sb.length() > 1){
				sb.append(',');
			}
			sb.append(cur.value.toString());
			cur = cur.next;
		}
		sb.append(']');
		return sb.toString();
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		DoubleLinkedList<String> dll = new DoubleLinkedList<String>();
		dll.addFirst("B")
		   .addFirst("A")
		   .addLast("D");
		dll.addAfter(dll.getNode("B"), "C");
		System.out.println(dll);		
	}

}
class Node {
	
	Node prev = null;
	Node next = null;
	Object value = null;
	
	public Node (Object value){
		this.value = value;
	}
	
	public String toString(){
		return value.toString();
	}
}
